Many of the tasks that are addressed by decision-making systems and artificial intelligence can be framed as constraint satisfaction problems. In this framework, the task is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of predicates, or constraints, that the variables must simultaneously satisfy. The set of variables and constraints is referred to as a constraint network. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to the problem is an assignment of a value to each variable from its domain that satisfies all of the constraints.
Constraint satisfaction methods have been found useful in a variety of applications, including:
Artificial intelligence
Robotic control
Temporal reasoning
Natural language parsing
Spatial reasoning
Test generation for software and hardware systems
Machine vision
Medical diagnosis
Resource allocation
Crew scheduling
Time tabling
Frequency allocation
Graph coloring.
For example, Lewin et al. describe a constraint satisfaction method for use in automated testing of memory access, in a paper entitled “Constraint Satisfaction for Test Program Generation,” in the proceedings of the IEEE 14th International Phoenix Conference on Computers and Communications (1995), pages 45–48, which is incorporated herein by reference. The authors use a constraint satisfaction algorithm to generate addresses and memory access instructions that provide effective verification of the design of a computer processor.
The constraint network can be viewed as a hypergraph, having a node for each variable and a hyper-edge for each constraint. These hyper-edges are referred to as arcs, wherein the members of such an arc are the variables that appear in the constraint to which the arc corresponds. An arc is said to be consistent if for any variable of the arc, and any value in the domain of the variable, there is a valid assignment of values to the other variables on the arc that satisfies the constraint represented by the arc. If every arc in the hypergraph is consistent, then the network is said to be arc-consistent.
In large networks, an exhaustive search for valid assignment of the variables can be extremely time-consuming. Various methods have been used to improve the efficiency of the search, such as pruning the search tree before or during the search, decision algorithms for choosing the next variable to instantiate or the next value to choose for the variable, and backtrack algorithms for deciding where to resume the search after reaching a “dead end.”
Recent research suggests that the most efficient general solutions for constraint satisfaction problems are algorithms based on maintaining arc consistency. These algorithms were introduced by Mackworth in an article entitled “Consistency in Networks of Relations,” published in Artificial Intelligence 8, pages 99–118 (1977), which is incorporated herein by reference. Arc consistency algorithms are based on the observation that given variables V1 and V2, with discrete domains D1 and D2, if x ∈ D1, and there is no y ∈ D2 that satisfies a given constraint Pij, imposed on V1, and V2, then x can be deleted from D1. This basic action of arc consistency algorithms is embodied in the Boolean procedure “REVISE”:
procedure REVISE((i,j)):beginDELETE ← falsefor each x ε Di doif there is no y ε Dj such that Pij(x,y)thenbegindelete x from Dl;DELETE ← trueendreturn DELETEendIt is also necessary, of course, that the variables have single node consistency, i.e., that they satisfy any applicable unary predicates in the constraint network. Mackworth also defines a simple procedure NC(i) for testing single node consistency.
Whenever REVISE is successful (i.e., when it results in reducing the domain of one of the nodes of the arc), it is necessary to determine whether the other arcs of the graph (G) are still consistent, and to REVISE their node domains as required to maintain consistency. Mackworth points out that it is not necessary to apply REVISE to all of the arcs in the graph, but only to those arcs for which the result of applying REVISE could possibly be changed from false to true. Thus, the arcs are maintained in a queue (Q), and the following algorithm is used to reapply REVISE to any of the arcs in the queue for which it is appropriate:
beginfor i ← 1 until n do NC(i);Q ← { (i,j) | (i,j) ∈ arcs(G), i ≠ j }while Q not empty dobeginselect and delete any arc (k,m) fromQ;if REVISE ((k,m)) then Q ← Q ∪{ (i, k) | (i, k) ∈ arcs (G), i ≠ k, i ≠ m}endend
Arc consistency algorithms may also be generalized to non-binary constraints, as described by Mackworth, for example, in an article entitled “On Reading Sketch Maps,” in Proceedings of the International Joint Conference on Artificial Intelligence (1977), pages 598–606. Other algorithms for maintaining arc consistency are also known in the art. A recent survey of these algorithms is presented by Bessiere et al., in “Using Constraint Metaknowledge to Reduce Arc Consistency Computation,” published in Artificial Intelligence 107(1), pages 125–148 (1999). Both of these articles are incorporated herein by reference.
Methods known in the art for solving constraint networks by maintaining arc consistency require that a constraint be given as a logical relation, represented as an explicit set of valid combination of variable values, or revealed through a predicate. Consequently, solutions of this type have been limited to problems and constraints for which this representation is feasible and provides for practical manipulation. Known methods suggest general schemes for consistency maintenance. A concrete consistency maintenance procedure should be reconstructed, following the given scheme, per constraint, or in some cases per constraint network. It is thus desirable to have a language for specifying constraints, and to be able to provide an automatic procedure for constructing consistency maintenance procedures for constraints specified using this language. A rudimentary grammar for constraint expressions is described by Offutt, in “An Integrated Automatic Test Data Generation System,” published in Journal of Systems Integration 1(3), pages 391–409 (1991), which is incorporated herein by reference. This scheme, however, deals only with unary constraints and is not suitable for maintaining arc consistency.
A number of constraint satisfaction systems are described in the patent literature. For example, U.S. Pat. No. 5,636,328, whose disclosure is incorporated herein by reference, describes methods and apparatus for finding values that satisfy a set of constraints, applied particularly to control of a robotic arm. The technique described in this patent is used in local search procedures for finding such constraint-satisfying values, with the aim of overcoming the tendency of such local search procedures to “get stuck” at certain points in the search. The technique dynamically adds weight to constraints in the set which are not satisfied by the current set of values and uses the weights of the constraints to determine the next set of values to be used in the local search. It is thus, essentially, a statistical method for solving constraint satisfaction problems, rather than an analytical method for maintaining arc consistency.
As another example, U.S. Pat. No. 5,617,510, whose disclosure is also incorporated herein by reference, describes a method, useful in computer-aided design, of identifying possible solutions to an over-constrained system having a collection of entities and constraints.